package likouJava;

import java.util.ArrayList;
import java.util.List;

public class 括号生成 {

    public List<String> generateParenthesis(int n) {
        List<String>res = new ArrayList<>();
        backtrack(res, new StringBuilder(), n, n);
        return res;
    }

    private void backtrack(List<String> res, StringBuilder path, int left, int right) {
        //当左右括号都用完表示生成应该有效的组合
        if (left == 0 && right ==0){
            res.add(path.toString());
            return;
        }

        //左边还能放
        if (left > 0){
            path.append('(');
            backtrack(res, path, left - 1, right);
            path.deleteCharAt(path.length() - 1); //回溯
        }

        //右括号要大于左括号才能放
        if (right > left){
            path.append(')');
            backtrack(res, path, left, right - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

}
